package com.otherTest.sort;


import org.junit.Test;


/**
 * 希尔排序（最小增量排序）
 *
 * @author Conceit
 * 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。
 * 希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
 * @version 1.0, 2017/5/12
 */
public class ShellSort {

//////////////////////////////////////////////////////////////////////////////////////////////

    @Test
    public void test1() {
        int[] sort = {1, 54, 6, 3, 78, 34, 12, 45, 56, 100};
        if (sort.length == 0 || sort == null) {
            System.out.println();
            return;
        }
        double d1 = sort.length;
        int temp = 0;
        while (true) {
            //向上取整 比如1.2取3
            d1 = Math.ceil(d1 / 2);
            //将下标分为5组d=5
            int d = (int) d1;
            for (int x = 0; x < d; x++) {
                for (int i = x + d; i < sort.length; i += d) {
                    int j = i - d;
                    temp = sort[i];
                    for (; j >= 0 && temp < sort[j]; j -= d) {
                        sort[j + d] = sort[j];
                    }
                    sort[j + d] = temp;
                }
            }
            if (d == 1)
                break;
        }
        //循环完成 遍历数组
        for (int i : sort) {
            System.out.println(i);
        }


    }
}



